#leetcode题目25：k个一组翻转链表
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：迭代


class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None

#TODO 链表类，注意在leetcode中没有这个，纯粹是acm模式下才需要这个
class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行

#核心解法
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy=ListNode(0)
        dummy.next=head
        end=prev=dummy


        def swap(prev,k,end):
            after=end.next
            move=prev.next
            prev.next=end
            temp=move.next
            end=move
            for i in range(k-1):
                tnext=temp.next
                temp.next=move
                move=temp
                temp=tnext
            end.next=after
            return end


        while True:
            try:
                for _ in range(k):
                    end=end.next
                prev=end=swap(prev,k,end)
            except:
                break
        return dummy.next




    #测试数据
    if __name__ == "__main__":
        list_str=[1,2,3,4,5]
        k=2
        #预期输出：[2,1,4,3,5]
        head=LinkList().initList(list_str)
        solution=Solution()
        LinkList().printlist(solution.reverseKGroup(head,k))


        list_str=[1,2,3,4,5]
        k=3
        #预期输出：[3,2,1,4,5]
        head=LinkList().initList(list_str)
        solution=Solution()
        LinkList().printlist(solution.reverseKGroup(head,k))
            

        